import java.util.*;

class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char val){
        this.val=val;
    }
}

public class MyBarTree {
    TreeNode root;
    public TreeNode creatTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;
       return A;
    }
    public void NLRPrint( TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val);
        NLRPrint(root.left);
        NLRPrint(root.right);
    }
    public void LNRPrint( TreeNode root){
        if(root==null){
            return;
        }
        LNRPrint(root.left);
        System.out.print(root.val);

        LNRPrint(root.right);
    }
    public void LRNPrint( TreeNode root){
        if(root==null){
            return;
        }

        LRNPrint(root.left);
        LRNPrint(root.right);
        System.out.print(root.val);
    }
//    public List<Integer> postorderTraversal(TreeNode root) {
//        List<Integer> list=new ArrayList<>();
//        if(root==null){
//            return list;
//        }
//        List<Integer> leftTree= postorderTraversal( root.left);
//        list.addAll(leftTree);
//
//
//        List<Integer> rightTree= postorderTraversal( root.right);
//        list.addAll(rightTree);
//        list.add(root.val);
//        return list;

     int count = 0;
public int size1(TreeNode root) {
    if(root==null){
        return 0;
    }
    count++;
    size1(root.left);
    size1(root.right);
    return count;
}

    public int size2(TreeNode root) {
        if(root==null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;
    }

    public int  getLeafNodeCount(TreeNode root){
    if(root==null){
        return 0;
    }
        if(root.left==null&&root.right==null){
            return 1;
        }

       return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }
    int leafCount=0;
    public void   getLeafNodeCount1(TreeNode root){
        if(root==null){
            return ;
        }
        if(root.left==null&&root.right==null){
            leafCount++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    int leafCount3=0;
    public int getLeafNodeCount3(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            leafCount3++;
        }
        getLeafNodeCount3(root.left);
        getLeafNodeCount3(root.right);
        return leafCount3;
    }
    public int  getLeafNodeCount2(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

    public int getKLevelNodeCount(TreeNode root,int k){

        if(root==null||k<0){
            return 0;
        }
        if(k==1){
                return 1;
            }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }
    public int getHight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftLength=getHight(root.left);
        int rightLength=getHight(root.right);
        return leftLength>rightLength?leftLength+1:rightLength+1;
    }
    public TreeNode find(TreeNode root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
       TreeNode ret= find(root.left,val);
        if(ret!=null){
            return ret;
        }
       ret= find(root.right,val);
        if(ret!=null){
            return ret;
        }

        return null;
    }
    public boolean isCompleteTree(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue= new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }

       while (!queue.isEmpty()){
           TreeNode top=queue.peek();
           if(top!=null){
               return false;
           }else {
               queue.poll();
           }
       }
       return true;

    }
    public void LevelOrder(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){return;}
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.println(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null){return ret;}
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            List<Integer> list=new ArrayList<>();
            while (size!=0){
                TreeNode cur=queue.poll();
              //  list.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
    //非递归前序遍历
    void preOrderNor(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                System.out.println(cur.val+" ");
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }
    //非递归中序遍历
    void inOrderNor(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);

                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.println(top.val+" ");
            cur=top.right;
        }
    }
//非递归后续遍历
    public void postOrderNor(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if(top.right==null||top.right==prev){//已经打印过的节点再不进行打印。
                stack.pop();
                System.out.println(top.val+" ");
                prev=top;//记录一下最近打印过的节点
            }else {
                cur=top.right;
            }
        }
    }
}
